import copy
import time
#计时
t1=time.time()
#待求解的数独，未知的用0
solve  = [[8, 1, 2, 7, 5, 3, 6, 4, 9],
          [9, 4, 3, 6, 8, 2, 1, 7, 5],
          [6, 7, 5, 4, 9, 1, 2, 8, 3],
          [1, 5, 4, 2, 3, 7, 8, 9, 6],
          [3, 6, 9, 8, 4, 5, 7, 2, 1],
          [2, 8, 7, 1, 6, 9, 5, 3, 4],
          [5, 2, 1, 9, 7, 4, 3, 6, 8],
          [4, 3, 8, 5, 2, 6, 9, 1, 7],
          [7, 9, 6, 3, 1, 8, 4, 5, 0]]

class sudoku:
    def debug(self):
        print(list)
    print("\n")

#检查重复,如果有重复，返回1；无重复，返回0
    def check_reption(self,list):
        flag=0
        for i in range(1,10):
            if list.count(i)>1:
                return 1
            else:
                flag+=flag
        if flag==9:
            return 0
    #检查横向重复
    def check_row(self,row):
        list = solve[row]
        r = self.check_reption(list)
        if r == 0:
            return 0
        else:
            return 1
    #检查纵向重复
    def check_column(self,column):
        list = []
        for num in solve:
            list.append(num[column])
        c = self.check_reption(list)
        if c == 0:
            return 0
        else:
            return 1

    #检查对应的每个九宫格有无重复值
    def check_square(self,x,y):
        x,y=y,x
        if x>=9 or y>=9:
            return
        square = []
        #将待求解的数组分割并放入square中
        for i in range(0+y//3*3, 3+y//3*3):
            for j in range(0+x//3*3, 3+x//3*3):
                square.append(solve[i][j])
        #检查square中9个数有无重复
        s = self.check_reption(square)
        if s==0:
            return 0
        else:
            return 1
    #将是否有重复的结果返回，无重复则返回0
    def check(self,x,y):
        r=self.check_row(x)
        c=self.check_column(y)
        s=self.check_square(x,y)
        result=r+c+s
        return result

    def get_next(self):
        i=0
        for list in solve:
            try:#获取0的位置
                column = list.index(0)   #列的位置为列表中0所在的位置
                row = solve.index(list)  #行所在位置为该列表所在的位置
                res = (row, column)
                return res         #返回坐标

            #得到时间
            except ValueError:
                i = i + 1
                if i == 9:
                    t2 = time.time()
                    print("总用时={}".format(t2 - t1))
                    exit(0)

    def coordinate(self,row,column):  # 坐标进行修正
        if row == 0 and column == -1:
            return
        if row == 8 and column == 9:
            return
        if column == -1:
            column = 8
            row = row - 1
        if column == 9:
            column = 0
            row = row - 1
        return (row,column)

    def get_last(self, row, column):
        solve[row].insert(column, 0)
        solve[row].pop(column + 1)
        column = column - 1  # 获得上一个已填值的行、列位置
        row, column = self.coordinate(row, column)  # 位置修正
        m = solve[row][column] * compare[row][column]
        while m != 0:
            column = column - 1
            row, column = self.coordinate(row, column)
            m = solve[row][column] * compare[row][column]
        return (row, column)

    def blank(self):
        try:
            row, column = self.get_next()
        except TypeError:  # 已填完
            exit(0)
        j = 0
        flag = 0
        for i in range(1, 10):
            solve[row].insert(column, i)
            solve[row].pop(column + 1)
            self.debug()
            m = self.check(row, column)
            if m == 0:  # 无重复值
                return
            else:
                j = j + 1
                if j == 9:
                    flag = 1
                    break
        if flag == 1:
            row, column = self.get_last(row, column)
            value = solve[row][column]
            self.debug()
            while value == 9:
                row, column = self.get_last(row, column)
                value = solve[row][column]
                self.debug()
            while value < 9:
                for k in range(value + 1, 10):
                    solve[row].insert(column, k)
                    solve[row].pop(column + 1)
                    self.debug()
                    r = self.check(row, column)
                    if r != 0:  # 有重复
                        if k == 9:
                            row, column = self.get_last(row, column)
                            value = solve[row][column]
                            self.debug()
                            while value == 9:
                                row, column = self.get_last(row, column)
                                value = solve[row][column]
                                self.debug()
                            break
                    else:
                        return


if __name__ == "__main__":
    compare = copy.deepcopy(solve)
    sudoku = sudoku()
    while 1:
        sudoku.blank()

